package bin_tree.heap;

import java.util.ArrayList;
import java.util.NoSuchElementException;

/**
 * @author shkstart
 * 基于数组实现的最大堆
 * 编号从0 开始，假设当前节点为i,i>0
 * 若是有左右孩子，保证，2i+1或2i+2 < data.length
 * left = 2i + 1
 * right = 2i + 2
 * @create 2022-10-27-21:43
 */
public class MaxHeap {

//    具体存储元素的动态数组
    private ArrayList<Integer> data ;
    public MaxHeap(){
        data = new ArrayList<>();
    }
    public MaxHeap(int capacity){
        data = new ArrayList<>(capacity);
    }
    /*
    将任意的整型数组调整为堆
     */
    public MaxHeap(int [] arr){
        data = new ArrayList<>(arr.length);
//        先将arr所有元素拷贝data中
        for(int i : arr){
            data.add(i);
        }
//        从最后一个非叶子节点开始进行元素下沉
        for (int i =  parent(data.size()-1); i>0; i--) {
            siftDown(i);
        }        
        
    }
    public int peekHeap(){
        if (data.size() == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        return data.get(0);
    }
    public boolean isEmpty(){
        return data.size()==0;
    }
    public void add(int val){
//        向数组末尾添加元素
        data.add(val);
//        调整当前堆的结构，使其满足最大堆的性质
        siftUp(data.size()-1);
    }
//    删除并取出最大元素
    public int extractMax(){
        if(isEmpty()){
            System.out.println("is empty");
            return -1;
        }
        int max = data.get(0);
//        将最后一个元素放到堆顶
        data.set(0,data.size()-1);
//        删除最后一个元素
        data.remove(data.size() - 1);
//        进行下沉操作
        siftDown(0);


        return max;
    }

//    下沉操作
    private void siftDown(int i) {
//        当左子树存在时
        while (left(i)<data.size()){
            int j = left(i);
//            当右子树存在时
            if (right(i) < data.size()) {
                int leftVal = data.get(left(i));
                int rightVal = data.get(right(i));
                if(leftVal<rightVal){
                    j = j+1;
                }
            }
            //此时j是左右孩子中最大值的索引
//            比较i 和 j 的值判断是否交换
            if(data.get(i)<data.get(j)){
                swap(i,j);
                i = j;
            }else{
//                当前节点已经大于左右孩子，下沉结束
                break;
            }
        }
    }


    //    元素上浮操作，i是需要上浮元素的索引
    private void siftUp(int i) {
        while(i>0&&data.get(i)>data.get(parent(i))){
//            交换i和parent(i)
            swap(i, parent(i));
//            交换之后,继续向上判断交换后的节点与新的父节点的关系
            i = parent(i);
        }

    }

    private void swap(int i, int parent) {
        int temp = data.get(i);
        int parentVal = data.get(parent);
        data.set(i,parentVal);
        data.set(parent,temp);

    }

    //    三个私有方法
//    获取当前父节点的索引
    private int parent(int k){
        return (k - 1) / 2;
    }
//    获取当前左子树节点的索引
    private int left (int k){
        return 2 * k + 1;
    }
//    获取当前右子树节点的索引
    private int right (int k){
        return 2 * k + 2;
    }


    @Override
    public String toString() {
       StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < data.size(); i++) {
            sb.append(data.get(i));
            if(i != data.size() - 1){
                sb.append(",");

            }


        }
        sb.append("]");
        return sb.toString();
    }
}
